package com.sort;

public class QuickSort {
    public void sort(int[] arr,int left,int right){
        if(left>right) return;
//        基准数，设置在左边，则后面从右边先开始移动
        int base = arr[left];
        int l = left,r = right;
        while(l!=r){
//            先从右开始找到比base值小的数
//            从右开始保证了最后交换基准数时的数是比基准数小的
            while(r>l && arr[r]>=base){
                r--;
            }
//            从左往右找，找到比基准数大的数
            while(l<r && arr[l]<=base){
                l++;
            }
//            交换l和r的数，使小数在左大数在右
            if(l<r){
                int tmp = arr[l];
                arr[l] = arr[r];
                arr[r] = tmp;
            }
        }
//        基准数归位
        arr[left] = arr[l];
        arr[l] = base;
//        递归，往左和往右继续排序
        sort(arr,left,l-1);
        sort(arr,l+1,right);
    }
}
